package com.taldh.algorithm.string;

import org.apache.commons.lang3.StringUtils;
import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class LengthOfLongestSubstringSolution {

    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     *
     * 示例 1:
     *
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     *
     * 输入: "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     *
     * 输入: "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param s
     * @return
     */

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
//        //1. 暴力法 时间复杂度：n^2 空间复杂度：n
//    int result = 0;
//    HashSet<Character> set = new HashSet<>();
//    for (int i = 0; i < s.length(); i++) {
//        set.add(s.charAt(i));
//        for (int j = i + 1; j < s.length(); j++) {
//            if (set.contains(s.charAt(j))) {
//                break;
//            }
//            set.add(s.charAt(j));
//        }
//        if (set.size() > result) {
//            result = set.size();
//        }
//        set.clear();
//    }
//
//
//    return result;

        //2. 暴力法优化，划窗
        // 时间复杂度：n 空间复杂度：n
//        int result = 0;
//        int i=0,j=0;
//        HashSet<Character> set = new HashSet<>();
//        while (i < s.length() && j < s.length()) {
//            if (!set.contains(s.charAt(j))) {
//                set.add(s.charAt(j++));
//                if (set.size() > result) {
//                    result = set.size();
//                }
//            } else {
//                set.remove(s.charAt(i++));
//            }
//        }
//
//        return result;

//        int n = s.length(), ans = 0;
//        Map<Character, Integer> map = new HashMap<>(); // current index of character
//        // try to extend the range [i, j]
//        for (int j = 0, i = 0; j < n; j++) {
//            if (map.containsKey(s.charAt(j))) {
//                i = Math.max(map.get(s.charAt(j)), i);
//            }
//            ans = Math.max(ans, j - i + 1);
//            map.put(s.charAt(j), j + 1);
//        }
//        return ans;

        int n = s.length(), ans = 0;
        int[] index = new int[128];  // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;

    }

    @Test
    public void test() {
        Assert.assertEquals(lengthOfLongestSubstring("abcadbcb"), 4);
    }

    public static void main(String[] args) {
        String str = "0wwsdferz";
        System.out.println(Arrays.toString(str.getBytes()));
    }
}